// 归并排序，自顶向下--传统的实现方式

// 暴露接口
export function mergeSort(nums: number[]): number[] {
    sort(nums, 0, nums.length - 1);
    return nums;
}
// 主排序逻辑，先把数组两两分开，再合并排序两个数组
function sort(nums: number[], start: number, end: number) {
    // 递归出口，只有一个元素的时候不用分裂
    if (start >= end) {
        return;
    }
    const mid = Math.floor((start + end) / 2);
    // 左右半边分裂
    sort(nums, start, mid);
    sort(nums, mid + 1, end);
    // 归并排序的过程
    merge(nums, start, mid, end);
}

// 归并逻辑，负责对两个有序的数组合并
function merge(nums: number[], start: number, mid: number, end: number) {
    const copyNums: number[] = [];// 待复制数组
    // 先复制要排序的数组
    for (let i = start; i <= end; i++) {
        copyNums[i] = nums[i];
    }
    // 基于双指针法进行归并，注意边界情况
    let left = start;
    let right = mid + 1;
    for (let i = start; i <= end; i++) {
        // 边界情况一，左数组已经被合并完
        if (left > mid) {
            nums[i] = copyNums[right];
            right++;
        } else if (right > end) {
            // 边界情况二，右数组已经被合并完
            nums[i] = copyNums[left];
            left++;
        } else if (copyNums[left] <= copyNums[right]) {
            // 正常情况，左边的数组比右边的数组小
            nums[i] = copyNums[left];
            left++;
        } else {
            // 正常情况，右边的数组比左边的数组小
            nums[i] = copyNums[right];
            right++;
        }
    }
}